package io.github.hadyang.leetcode.random;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 计算右侧小于当前元素的个数
 *
 * <p>给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。
 *
 * <p>示例:
 *
 * <p>输入: [5,2,6,1] 输出: [2,1,1,0] 解释: 5 的右侧有 2 个更小的元素 (2 和 1). 2 的右侧仅有 1 个更小的元素 (1). 6 的右侧有 1 个更小的元素
 * (1). 1 的右侧有 0 个更小的元素.
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author haoyang.shi
 * @date 2019-10-25
 */
public class Q315 {

  private int[] index;
  private int[] helper;
  private int[] count;

  public List<Integer> countSmaller(int[] nums) {
    List<Integer> res = new ArrayList<>(nums.length);

    index = new int[nums.length];
    helper = new int[nums.length];
    count = new int[nums.length];
    for (int i = 0; i < index.length; i++) {
      index[i] = i;
    }

    merge(nums, 0, nums.length - 1);

    for (int i = 0; i < count.length; i++) {
      res.add(i, count[i]);
    }
    return res;
  }

  private void merge(int[] nums, int s, int e) {
    if (s == e || s > e) return;
    int mid = (s + e) >> 1;

    if (s < mid) {
      merge(nums, s, mid);
    }

    if (mid + 1 < e) {
      merge(nums, mid + 1, e);
    }

    int i = s, j = mid + 1;
    int hi = s;
    while (i <= mid && j <= e) {
      if (nums[index[i]] <= nums[index[j]]) {
        // 右侧出
        helper[hi++] = index[j++];
      } else {
        // 左侧出 计数
        count[index[i]] += e - j + 1;
        helper[hi++] = index[i++];
      }
    }

    while (i <= mid) {
      //左侧出
      helper[hi++] = index[i++];
    }

    while (j <= e) {
      // 右侧出
      helper[hi++] = index[j++];
    }

    if (e + 1 - s >= 0) {
      System.arraycopy(helper, s, index, s, e + 1 - s);
    }
  }

  private void mergeAndCount(int[] num, int s, int e) {}

  @Test
  public void test() {
    int[] nums;
    nums = new int[] {5, 2, 6, 1};
    System.out.println(countSmaller(nums));

    nums = new int[] {5, 2, 6, 1, 3, 7, 3, 1, 2};
    System.out.println(countSmaller(nums));

    nums = new int[] {5, 2, 6, 1, 3, 7};
    System.out.println(countSmaller(nums));
  }
}
